HW#3 --- last modified January 01 1970 00:00:00..

Solution set.

This homework has been extended from Oct. 25 to Oct. 28. However, people who want to be graded based on what they had on the Oct. 25 will receive two extra bonus points after curving.

Due date: Oct 28

Files to be submitted:
  problems.doc
  sortmerge.java

Purpose: To gain familiarity with how DB catalogs work, and to gain experience with query processing techniques.

Specification:

Be aware that the current limit on submitted file size is 1.5MB.

Do the following problems out of E&R 17.14, 18.13, 18.14, 18.22 and submit them in problems.doc. Write a java program to implement the sort merge algorithm of Figure 18.2. Your algorithm will be tested from the command-line with a line like:

java sortmerge num_blocks_buffer block_size_byte in_file out_file

Ex:

java sortmerge 5 2048 myfile.txt sorted.txt

To determine the number size of the file so you can figure out the number of blocks use the length() methods in the java class File. Note the block size above does not neccessarily correspond to the block size actually used for the file. You can assume that the test file consists of a sequence of strings of A's and B's, each string being up to 80 characters long with a `\r\n' between strings. All strings (which are our records) in a given file can be assumed to be of the same length. You can also assume the block size is bigger than the length of these strings/records. Be forwarned, if your code attempts to read in the whole file into memory, rather than restricting yourself to num_blocks*block_size_bytes bytes you will receive 0 for this part of the homework.

To keep things simple I will choose test parameters to avoid spanned records; howver, if your code handles spanned records correctly then you can receive one bonus point to your grade after curving. Please indicate at the start of your code if you want the grader to test on spanned inputs. Below is some code that can be used to generate random rows:

// RandomStrings.java -- program used to generate random string data for CS157b Hw3 Problem 5.

import java.util.*;
import java.io.*;

/** 
   This class consists of a bunch of public static methods used to generate
   random row data for the CS157B HW3 Problem 5.

   Typically one would run this program from the command line with a line like:

   java RandomStrings string.DAT 80 1000

   Here string.DAT is the file to write the random data to, 80 is the number of characters
   of each records, and 1000 is the number of rows of random data to generate. 

   @author Chris Pollett
   @version 1.0.2002

*/
public class RandomStrings
{

   /** 
       Creates numRows rows of random data each row of length stringLength and save it in a file named 
       by String fileName.

       @param fileName -- filename to store random row data in
       @param stringLength -- length of a row (not including end of line chars)
       @param numRows -- number of rows of data to create

   */
   public static void createData(String fileName, int stringLength, int numRows)
   {

      try
      {
          PrintStream out = new PrintStream(
             new FileOutputStream(fileName));

          for(int i = 0; i < numRows; i++)
          {

             StringBuffer bRow = new StringBuffer(BUFLEN);
             createRow(stringLength, bRow);
             
             out.println(bRow.toString());
           }

          out.close();                    
      }
      catch(IOException ie)
      {
         ie.printStackTrace();
      }

   } 

   /** 
      Creates one row of random data given the parameters supplied.
      
	  @param stringLength -- length of a row
      @param buf -- presumed empty StringBuffer in which to append random row.

   */
   public static void createRow (int stringLength, StringBuffer buf)
   {

      for(int i=0; i < stringLength; i++)
      {
        int preDigit = (int)(Math.random()*2)+65;
        String digit = ""+(char)preDigit;
		buf.append(digit);
      }

   }

   /** 
      Calls createData with the command line arguments to generate the random
      data

      @param args - array of command line arguments
   */
   public static void main (String [] args)
   {

      if(args.length < 3)
      {
         System.out.println("To use:");
         System.out.println("java RandomStrings fileName stringLength numRows");         
         System.out.println("where fileName is the file you'd like data written to");
         System.out.println("stringLength is the length of each record");
         System.out.println("and numRows is how many rows you'd like generated.");
      }

      else
         createData(args[0], Integer.parseInt(args[1]), Integer.parseInt(args[2]));
   }

	public static final int BUFLEN = 80; //presumed max size of a row
 
}

Point Breakdown